#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 500010, INF = -1e9;
int a[N], f[N], h[N], g[N];
int T, n;
int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        f[0] = f[n + 1] = INF;
        g[0] = h[n + 1] = INF;
        for (int i = 1; i <= n; i++)
        {
            f[i] = a[i] + max(f[i - 1], 0);
            g[i] = max(f[i], g[i - 1]);
        }
        for (int i = n; i >= 1; i--)
        {
            f[i] = a[i] + max(f[i + 1], 0);
            h[i] = max(f[i], h[i + 1]);
        }
        int res = INF;
        for (int mid = 1; mid < n; mid++)
        {
            res = max(res, g[mid] + h[mid + 1]);
        }
        cout << res << endl;
    }
    return 0;
}